import java.util.Random;



class Solution {
    public int[] sortArray(int[] nums) {
        func(nums,0,nums.length-1);
        return nums;
    }

    public void func(int[] nums,int l,int r){
        if(l>=r) return;
        int n=nums[new Random().nextInt((r-l+1))+l];
        int left=l-1,right=r+1,i=l;
        while(i<right){
            if(nums[i]<n) swap(nums,i++,++left);
            else if(nums[i]==n) i++;
            else swap(nums,i,--right);
        }
        func(nums,l,left);
        func(nums,right,r);

    }

    public void swap(int[] nums,int i,int j){
        int t=nums[i];
        nums[i]=nums[j];
        nums[j]=t;

    }
}





public class Main {


    public static void main(String[] args) throws InterruptedException {
        Object locker = new Object();
        Thread t1 = new Thread(new WaitTask(locker));
        Thread t2 = new Thread(new NotifyTask(locker));
        t1.start();
        Thread.sleep(1000);
        t2.start();
    }


    static class WaitTask implements Runnable {
        private Object locker;

        public WaitTask(Object locker) {
            this.locker = locker;
        }

        @Override
        public void run() {
            synchronized (locker) {
                while (true) {

                    try {
                        System.out.println("wait 开始");
                        locker.wait();
                        System.out.println("wait 结束");
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }
    }

    static class NotifyTask implements Runnable {
        private Object locker;

        public NotifyTask(Object locker) {
            this.locker = locker;
        }

        @Override
        public void run() {
            synchronized (locker) {
                System.out.println("notify 开始");
                locker.notify();
                System.out.println("notify 结束");
            }
        }
    }

}